package com.niuke;


import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

/**
 * 36. 计算疫情扩散时间
 * 类似 宜居星球改造计划
 * https://blog.csdn.net/BYZLZ119/article/details/131064140
 */
public class NiukeMoni36 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine();
        List<Integer> map = new ArrayList<>();
        int pos = 0;
        String token;
        while ((pos = input.indexOf(",")) != -1) { // 将输入字符串转换为一维数组
            token = input.substring(0, pos);
            map.add(Integer.parseInt(token));
            input = input.substring(pos + 1);
        }
        map.add(Integer.parseInt(input));
        System.out.println(getResult(map)); // 输出感染天数
    }

    public static int getResult(List<Integer> map) {
        int n = (int) Math.sqrt(map.size());

        int[][] matrix = new int[n][n]; // 将一维数组转换为二维矩阵

        Queue<int[]> q = new LinkedList<>(); // 用队列存储感染区域

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = map.get(i * n + j); // 将一维数组转换为二维矩阵
                if (matrix[i][j] == 1) q.offer(new int[]{i, j}); // 将感染区域加入队列
            }
        }

        if (q.isEmpty() || q.size() == map.size()) { // 判断特殊情况
            return -1;
        }

        int healthy = map.size() - q.size(); // 记录未感染区域数量

        int[][] offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 记录四个方向的偏移量

        int day = 0; // 记录感染天数
        while (!q.isEmpty() && healthy > 0) { // 当队列不为空且还有未感染区域时，进行循环
            int[] tmp = q.poll(); // 取出队首元素
            int x = tmp[0], y = tmp[1]; // 获取队首元素的坐标
            day = matrix[x][y] + 1; // 记录感染天数

            for (int[] offset : offsets) { // 遍历四个方向
                int newX = x + offset[0]; // 新的横坐标
                int newY = y + offset[1]; // 新的纵坐标

                if (newX < 0 || newX >= n || newY < 0 || newY >= n) continue; // 判断边界

                if (matrix[newX][newY] == 0) { // 如果该区域未感染
                    healthy--; // 未感染区域数量减一
                    matrix[newX][newY] = day; // 标记该区域已感染
                    q.offer(new int[]{newX, newY}); // 将该区域加入队列
                }
            }
        }

        return day - 1; // 返回感染天数
    }
}



